//Wed Jun 15 17:02:55 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int INF = 500000001;
const int EMPTY = 26;

class PalindromizationDiv1 {
public:
	int changeCost[27][27];
	int matchCost[27][27];
	int dp[55][55];
	string word;
	int rec(int, int);
	int getMinimumCost(string, vector <string>);
};

int PalindromizationDiv1::rec(int a, int b){
	int &ret = dp[a][b];
	if(ret != -1) return ret;
	if(a == b){
		ret = 0;
		return ret;
	}
	
	int ca = word[a] - 'a';
	int cb = word[b] - 'a';
	if(a == b-1) return ret = min(matchCost[ca][cb], min(rec(a+1,b) + matchCost[ca][EMPTY], rec(a,b-1) + matchCost[cb][EMPTY]));
	ret = INF;
	
	int x, y;
	
	x = matchCost[ca][cb];
	y = rec(a+1, b-1);
	if(x < ret - y) ret = min(INF, x + y);
	
	x = min(matchCost[ca][EMPTY], matchCost[EMPTY][ca]);
	y = rec(a+1, b);
	if(x < ret - y) ret = min(INF, x + y);
		
	x = min(matchCost[cb][EMPTY], matchCost[EMPTY][cb]);
	y = rec(a, b-1);
	if(x < ret - y) ret = min(INF, x + y);
	
	return ret;
}

int PalindromizationDiv1::getMinimumCost(string w, vector <string> op) {
	memset(dp, -1, sizeof(dp));
	this->word = w;
	
	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			changeCost[i][j] = INF;
			matchCost[i][j] = INF;
		}
	}
	
	for(int i=0; i<27; i++){
		changeCost[i][i] = 0;
	}
	
	for(int i=0; i<op.size(); i++){
		stringstream s(op[i]);
		string str;
		char ca, cb;
		s >> str >> ca;
//		cout << str << "," << ca << endl;
		if(str == "add") s >> changeCost[EMPTY][ca-'a'];
		else if(str == "erase") s >> changeCost[ca-'a'][EMPTY];
		else {
			s >> cb;
			s >> changeCost[ca-'a'][cb-'a'];
		}
	}
	
	for(int k=0; k<27; k++){
		for(int i=0; i<27; i++){
			for(int j=0; j<27; j++){
				int x = changeCost[i][k];
				int y = changeCost[k][j];
				int &z = changeCost[i][j];
				if(x < z - y) z = min(INF, x+y);
			}
		}
	}
	
//	for(int i=0; i<27; i++){
//		for(int j=0; j<27; j++){
//			cout << changeCost[i][j] << ", ";
//		}
//		cout << endl;
//	}
	
	for(int i=0; i<27; i++){
		for(int j=0; j<27; j++){
			for(int k=0; k<27; k++){
				int x = changeCost[i][k];
				int y = changeCost[j][k];
				int &z = matchCost[i][j];
				if(x < z - y) z = min(INF, x+y);
			}
		}
	}

//	for(int i=0; i<27; i++){
//		for(int j=0; j<27; j++){
//			cout << changeCost[i][j] << ", ";
//		}
//		cout << endl;
//	}
	
	int N = word.size();
	int x = rec(0, N-1);
//	for(int i=0; i<N; i++) {
//		for(int j=0; j<N; j++) cout << dp[i][j] << ", ";
//		cout << endl;
//	}
	return ((x>=INF)? -1 : (int)x);
}

//Powered by [KawigiEdit] 2.0!
